package com.le.medium.class5;

import org.junit.Test;

import java.util.Arrays;

/**
 * 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容 量为w。
 * 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
 * 牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法(总体积为0也 算一种放法)。
 */
public class Problem06_CompriseWays {

    public static int ways(int[] arr, int m) {
        if (arr == null || arr.length == 0 || m < 0) {
            return 0;
        }
        return process(arr, m, 0, 0);
    }

    // 递归
    private static int process(int[] arr, int m, int i, int weight) {
        if (i == arr.length) {
            return weight <= m ? 1 : 0;
        }
        return process(arr, m, i + 1, weight + arr[i]) + process(arr, m, i + 1, weight);
    }

    // 动态规划
    public static int ways1(int[] arr, int w) {
        if (arr == null || arr.length == 0 || w < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length][w + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= w; i++) {
            dp[0][i] = i >= arr[0] ? 2 : 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < w + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - arr[i] >= 0) {
                    dp[i][j] += dp[i - 1][j - arr[i]];
                }
            }
        }
        return dp[arr.length - 1][w];
    }

    public static int[] generateArray(int size) {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = (int) (Math.random() * 100) + 1;
        }
        return res;
    }

    @Test
    public void test() {
//        int[] arr = { 4, 3, 2, 9 };
//        int w = 8;

        System.out.println("hello");
        for (int i = 1; i < 1000; i++) {
            int[] ints = generateArray(20);
            int k = (int) (Math.random() * 100) + 1;
            if (ways(ints, k) != ways1(ints, k)) {
                System.out.println("no");
                System.out.println(Arrays.toString(ints));
                System.out.println(k);
            }
        }
//        System.out.println(ways(arr,w));
//        System.out.println(ways1(arr,w));
    }
}
